Within a processor that functions according to a serial execution model, a program counter sequences through instructions one-by-one, issuing one instruction before starting the next. As a result, any parallelism that could be controlled by a microprogram of the processor is limited to the execution of a single instruction. By way of contrast, pipelined processors do not follow a serial execution model. Within a pipelined processor, at any one time, one portion of a given instruction is processed in the pipeline.
However, other portions of a number of different instructions are also simultaneously processed to provide concurrent execution of portions of a number of instructions. Accordingly, a pipeline is a structure that consists of a sequence of stages through which instructions may flow with the property that new instructions or operations can be initiated at the start of the pipeline while other operations are in progress within the pipeline. Hence, by using pipelined execution of instructions within processors, multiple instructions may overlap processing in different pipeline stages to improve overall throughput of instructions and speed up program execution time.
Pipelined processors encounter situations known as hazards where a subsequent instruction cannot execute until the completion of a previous instruction. Examples include data hazards where a subsequent instruction needs to see the side effects of a previous instruction in order to execute. A further example is resource hazards where the later instruction needs to use a resource that continues to be occupied by an earlier instruction. Collectively, the various hazards described herein are referred to as “instruction blocking conditions”. Conventionally, the situations are handled by using a stalling technique.
In the stalling technique, instructions are not allowed to advance to the next pipeline stages until the earlier, hazard causing instruction has itself advanced to a stage that no longer creates the hazard. Unfortunately, a stall scheme needs to detect that a pipeline advance would cause a hazard in the future and has to prevent the advance. Further, a stall scheme has to stall all instructions in the pipeline behind the hazard victim to prevent instruction loss. This implies a large fan out of the stall condition to enable inputs of pipeline latches presenting another requirement for the early determination of the stall condition.
Usually in high frequency designs, the earlier a condition has to be determined, the more likely it is to become a critical timing path. Furthermore, more recent processors have pipelines, such as cache and memory access pipelines, where dependencies between instructions and adjacent pipelines frequently do not exist. As a result, the cost of stalling an entire pipeline to prevent a hazard, especially one with many stages, is high in terms of performance because it prevents forward progress of hazard free instructions. Therefore, there remains a need to overcome one or more of the limitations in the above-described, existing art.